#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <map>
#include <numeric>
#include <vector>

#include <cstdlib>
#include <ctime>

/* k_median 相关的头文件 */
#include <chrono> // std::chrono::high_resolution_clock
#include <string> // std::string
#include <fstream> // std::ifstream, std::ofstream
#include <iostream> // std::cout
#include <sstream>
#include <map>
#include <set>
#include <unordered_set>
#include <cfloat>
#include <vector>
#include <tuple>
#include <utility>

#include "typed_directed_graph.h"
#include "k_median.h"
#include "LNB.h"
#include "assistant.h"
#include "HashPair.h"
#include "BAB.h"


int main(int argc, char* argv[])
{
	if (argc < 2)
	{
		std::cerr << "命令行参数不足\n";
		return 1;
	}
	// 记录时间
	auto begin_all = std::chrono::steady_clock::now();

	int k = 0;  // 可以替换的设施数量
	int fnum = 0;  // 原来的设施数量
	std::unordered_map<int, char> ftype;  // 设施编号与设施类型之间的对应关系，设施类型为：'F' 和 'C'
	std::vector<int> fac_id;  // 所有的设施编号
	std::unordered_map<int, std::unordered_map<int, double>> distance;  // 用户与设施之间的距离矩阵
	wh::Config config;

	/*****************************************
	/* 以下这个代码块用来初始化距离矩阵，以及上述的其它变量
	 * 设置成单独的代码块，可以实现内存的自动释放
	 *****************************************/
	{
	    // 首先读取配置文件的相关信息并保存
		config.init(argv[1]);

		// 读入设备信息到 facility_info_map 中，将候选设施信息读入 candidate_info_map 中
		wh::facility_info_map  facility_info;
		std::ifstream fin(config.facility_file);
		wh::check_file(fin, config.facility_file); // 读入已有设施信息
		{
			int a, b, c;
			double d, e;
			while (fin >> a >> b >> c >> d >> e)
			{
				facility_info[a] = std::make_tuple(b, c, d, e);
				wh::eat_line(fin);
			}
			fin.close();
		}

		const int f_number = facility_info.size();  // 已有设施的数量

		// 读入候选设施信息，候选设施和已有设施保存在同一个数据结构中，通过 +10000 进行区分
		// 设置一个数据结构保存所有候选设施信息，方便之后将其删除
		std::unordered_set<int> candidate_id;
		{
			fin.open(config.candidate_file);
			int a, b, c;
			double d, e;
			while (fin >> a >> b >> c >> d >> e)
			{
				facility_info[a] = std::make_tuple(b, c, d, e);
				candidate_id.insert(a);
				wh::eat_line(fin);
			}
			fin.close();
		}

		// 初始化图结构，并部署设备（所有设备，包括已有设备和候选设备）
		typed_directed_graph graph;
		graph.set_to_bidirectional(!config.is_directed_graph);
		graph.init_graph(config.edge_file.c_str());
		graph.deploy_facilities(facility_info);
		if (!graph.get_is_facilities_deployed()) // 检查是否成功部署图
		{
			std::cerr << "I can't deploy the facilities.\n";
			std::cin.get();
			return 1;
		}

		// 将参考位置信息读入到 ref_info 中，并且初始化 dist_old
		// dist_old  存储着每个当前情况下，每个参考位置与距离最近设施之间的距离
		wh::ref_nearest_dist_map dist_old;// 存储每个参考位置当前以及上一步时最近设施的距离
		wh::reference_info_list ref_info; // 记录所有参考位置的信息
		fin.open(config.refloc_file);
		wh::check_file(fin, config.refloc_file);
		{
			int a, b, c; // id vs_id ve_id
			double d, e, f;// vs_dist ve_dist prob
			while (fin >> a >> b >> c >> d >> e >> f)
			{
				ref_info.push_back(std::make_tuple(a, b, c, d, e, f));
				dist_old[a] = DBL_MAX;
				wh::eat_line(fin);
			}
			fin.close();
		}

		// 读入设备信息，并且初始化 dist_map，fac_ref_dist
		// dist_map 记录着设施到所有用户的总距离，fac_ref_dist则记录着每个参考位置到设施的路网距离
		std::map<int, double> dist_map;
		wh::fac_ref_dist_map fac_ref_dist;
		for (auto& f : facility_info)
		{
			dist_map[f.first] = 0;
			for (auto i : ref_info)
				fac_ref_dist[f.first][std::get<0>(i)] = DBL_MAX; // std::get<0>(i) 得到的是参考位置id
		}

		// 遍历所有的参考位置，计算参考位置到各个设施之间的路网距离
		for (auto i : ref_info)
		{
			int refloc_id = std::get<0>(i);
			int vs_id = std::get<1>(i);
			int ve_id = std::get<2>(i);
			double dist_vs = std::get<3>(i);
			double dist_ve = std::get<4>(i);
			double prob = std::get<5>(i);

			std::cout << refloc_id << std::endl;
			vertex refloc_v(refloc_id, 'r'); // 在图中将参考位置作为一个点插入
			std::vector<directed_edge> removed_edges, inserted_edges;
			graph.insert_vertex(vertex(vs_id, 'v'), vertex(ve_id, 'v'), refloc_v, dist_vs, dist_ve, &removed_edges, &inserted_edges,
				false); // "false" 意味着不去替换参考位置覆盖的点，我们将会为它创建一个虚拟的点 
			graph.dijkstra(refloc_v, dist_map, fac_ref_dist, facility_info.size(), prob);
			graph.restore_graph(refloc_v, removed_edges, inserted_edges);
		}

		// 构造距离矩阵
		for (auto& p1 : fac_ref_dist)
		{
			int f_id = p1.first;
			for (auto& p2 : p1.second)
				distance[p2.first][f_id] = p2.second;
		}

		for (auto& p : facility_info)
		{
			if (candidate_id.count(p.first))
				ftype[p.first] = 'C';
			else
				ftype[p.first] = 'F';
			fac_id.push_back(p.first);
		}

		k = config.K;
		fnum = f_number;
	}
	std::ofstream fout_time(config.time_file);
	if (!fout_time.is_open())
	{
		std::cerr << "打开时间记录文件失败\n";
		return 1;
	}
	fout_time << "构造距离矩阵的时间为(ms): " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - begin_all).count() << "\n";
    std::cout << "构造距离矩阵的时间为(ms): " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - begin_all).count() << "\n";
	begin_all = std::chrono::steady_clock::now();

	std::ofstream fout(config.result_file);
	/* 程序的核心部分，从 1 到 k ，循环 k 次，对 k 个设施进行重选址*/
	for (int i = 1; i <= config.K; i++)
	{
		/* 读入初始的设备 id，确定当前的上界，同时确定每个设施被多少个用户访问 */
		std::vector<int> init_id; // 当前的最优的设施集合
		if (config.fac_id.size())  // 如果配置文件里有指定了 fac_id 的文件
			init_id = init_fac_id(config.fac_id, i);  // i 代表读入第 i 行
		else
			init_id = init_fac_id();

		std::unordered_map<int, int> visit_num;  // 记录每个设施 id 被多少个用户访问
		double alpha = calculate_original_dist(distance, init_id, visit_num);  // 初始化 alpha 以及  visit_num

		std::vector<HashPair<int>> num2id;  // 记录每个数量和 id 之间的对应关系
		for (auto& p : visit_num)
		{
			num2id.push_back(HashPair<int>(p));
		}
		std::sort(num2id.begin(), num2id.end());

		std::unordered_map<int, bool> branch_flag;  // 记录某个设施是否已经进行了分支
		for (int i : fac_id)
			branch_flag[i] = false;

		/* 初始化分支定界算法的上下文环境 */
		BAB worker;
		worker.distance = &distance;  // ## 这样的代表并不是每次循环都真正的进行了更新，这样写主要是为了保持一致性
		worker.branch_flag = &branch_flag;
		worker.current_id = &init_id;
		worker.fac_id = &fac_id;  // ##
		worker.ftype = &ftype;  // ##
		worker.visit_num = &visit_num;
		worker.num2id = &num2id;
		worker.k = i;
		worker.fnum = fnum;
		worker.alpha = alpha;
		if (config.rate > 0.0)  // 如果配置文件中设置了 rate，将其更新到 worker 中
			worker.rate = config.rate;

		/* 设置程序的输出流，如果文件打开了，就向文件中输出内容，否则默认向标准输出进行输出 */
		if (fout.is_open())
			worker.fout = &fout;

		if (worker.init())
		{
			worker.run();
		}

		if (fout.is_open())
		{
			fout << worker.alpha << std::endl;
			fout << "##########\n";  // 标记一个 k 的结束
		}
		else
		{
			std::cout << worker.alpha << std::endl;
			std::cout << "##########\n";
		}

		fout_time << "对 " << i << " 个设施进行重选址花费的时间为: " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - begin_all).count() << "\n";
		begin_all = std::chrono::steady_clock::now();
	}

	fout_time.close();
	if (fout.is_open())
		fout.close();
}